#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <semaphore.h>
#include "memory.h"
#include "grow_memory.h"
#include "get_memory.h"
#include "release_memory.h"

extern int info[MAX_L];
extern int sum;
extern Buddy* p_tree;
extern void* base;
extern sem_t g_sem;


void *grow_memory( void *p, int new_size )
{
    mem_header_t *pointer = (mem_header_t *)p;
    pointer = &pointer[-1];             // get the address of the header
	printf("Grow the memory block with header address: %p--------------------------\n", pointer);
	
    long unsigned int p_value = (long unsigned int) pointer;
    Buddy *node = (Buddy *)p_tree;
    Buddy *tree = (Buddy *)p_tree;
    Buddy *grow_node = NULL;

	int need = new_size + sizeof(mem_header_t);
    int one = 1;
    int l, l0, old_size;

    // find the tree node with manage info.
    l0 = 0; 
	l =0;
    int index = 0;           // for bit operation to index the node on a level

	sem_wait(&g_sem);

    while (! grow_node) {
        if (p_value == (long unsigned int)node->p) {
            if (node->left ==NULL ) {
                if (node->right ==NULL) {
                    grow_node = node;
					printf("found the node at level %d\n", l0);
                }
                else {
				    printf("Invalid access!\n");
				    exit(1);            // right occurpied, misrelease
				}
            }
            else {
                node = node->left;
                l0++;
                index = index<<1;
				printf("look left to level %d\n", l0);
            }
        }
        else if (node->right !=NULL ) {
            if (p_value >= (long unsigned int)(node->right->p)) {
                node = node->right;
                l0++;
                index = (index<<1) +1;
				printf("look right to level %d\n", l0);
            }
            else { //if (p_value < (long unsigned int)(node->right->p)) {
                node = node->left;
                l0++;
                index = index<<1;
            }
        }
		else {                  // right == NULL
			node = node->left;
			l0++;
			index = index<<1;
		}

    }
    printf("Found the node to be grown: %p\n", grow_node->p);
	printf("The block need to grow is on level %d\n", l0);


    // compute which level should the the goal block be on
    l = 0;          // to mark the level of suitable size.
	
	if(need>sum) {
		printf("Can't grow more than memory limit\n");
sem_post(&g_sem);
		return NULL;
	}	
	
    while (need <= sum/(one<<l)) {
        if (need <= sum/(one<<(l+1)))
            l++;
        else
            break;
    }
    printf("The goal block should be on level %d\n", l);
	
    // find the level difference
    int dif = l0 - l;

    // if truncate or requested size is smaller than current memory blcok, just modify the header
    if (dif <= 0) {
	    old_size = pointer->size;
        pointer->size = new_size;		
sem_post(&g_sem);
        return p;
    }

    // if the new_size > size

    // if the grow can be done from current point, then stay to grow 
    // else, try to release and malloc
    int stay = 1;       // represent if the memory can grow staying at original address
    int i;
    int level_head = one<<l0;
    int ind = index;
    for (i=0; i<dif; i++) {
        if (ind%2 == 1 || (tree[level_head + ind].p != NULL && ind<=level_head)) {   // check if current is right node || next block is used [level_head-1+ index+1]
		    printf("Right node or the left node's buddy Tree [%d] is already used\n", level_head + ind);
            stay = 0;
            break;
        }
        level_head = level_head/2;
        ind = ind/2;
    }
    if (stay) {     // ok to stay here to grow
	    printf("OK to grow at original position\n");
		int tmp_l = l0;
        level_head = one<<l0;
        ind = index;
        for (i=0; i<=dif; i++) {         // destroy node from current level, till goal level
            tree[level_head -1 +ind].left = NULL;
            tree[level_head -1 +ind].right = NULL;

            if (i < dif)
			{
				tree[level_head -1 +ind].p = NULL;      // the pointer in goal level not set to NULL
			}
			info[tmp_l]++;
			tmp_l--;
			
            level_head = level_head/2;  
            ind = ind/2; 

        }
        // modify header info
        mem_header_t *tmp = tree[level_head -1 +ind].p;
		old_size = tmp->size;
        tmp->size = new_size;
sem_post(&g_sem);
        return (void *)&tmp[1];
    }
    else {

        // if the goal level has blocks available
        if (info[l] > 0) {
		    printf("Grow at new place.\n");
            void *result_p = get_memory(new_size);
            memcpy(result_p, p, new_size);
            release_memory(p);
            printf("The new address for the growed node: %p\n", result_p);
sem_post(&g_sem);
            return result_p;
        }
        else
		{
		    printf("Can't grow!\n");
sem_post(&g_sem);
            return NULL;	
		}
    }


}




